package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/">211. 添加与搜索单词 - 数据结构设计</a>
 */
public class Solution211 extends BaseSolution {

class WordDictionary {
    class Model {
        boolean hasEnd = false;
        final Map<Character, Model> nexts;

        public Model() {
            nexts = new TreeMap<>();
        }

        void add(String str, int index) {
            if (index >= str.length()) {
                hasEnd = true;
                return;
            }
            char c = str.charAt(index);
            Model next = nexts.get(c);
            if (next == null) {
                next = new Model();
                nexts.put(c, next);
            }
            next.add(str, index + 1);
        }

        boolean find(String str, int index) {
            if (index >= str.length()) {
                return hasEnd;
            }
            char c = str.charAt(index);
            if (c != '.') {
                Model next = nexts.get(c);
                if (next == null) {
                    return false;
                } else {
                    return next.find(str, index + 1);
                }
            } else {
                for (Model next : nexts.values()) {
                    if (next.find(str, index + 1)) {
                        return true;
                    }
                }
                return false;
            }
        }
    }

    Model root;

    public WordDictionary() {
        root = new Model();
    }

    public void addWord(String word) {
        root.add(word, 0);
    }

    public boolean search(String word) {
        return root.find(word, 0);
    }
}

    public static void main(String[] args) {
        Solution211 solution = new Solution211();
    }
}